//
// Created by 周智超 on 2020/6/28.
//

#ifndef STRUCTURE_TREE_H
#define STRUCTURE_TREE_H
#include "normal.h"
#include <stdlib.h>
#include <iostream>

typedef struct BTNode {
    int data;
    struct BTNode* lchild;
    struct BTNode* rchild;
    struct BTNode* parent;
}BTNode;

BTNode* initBT(int data, BTNode* lchild, BTNode* rchild)
{
    BTNode* root;
    root = (BTNode*)malloc(sizeof(BTNode));
    root->data = data;
    root->lchild = lchild;
    root->rchild = rchild;
    return root;
}

void linkParent(BTNode *root, BTNode *parent)
{
    if(root == NULL)
    {
        return;
    }
    root->parent = parent;
    linkParent(root->lchild, root);
    linkParent(root->rchild, root);
}
void printPath(BTNode *root)
{
    while (root != NULL)
    {
        std::cout << root->data << " ";
        root = root->parent;
    }
    std::cout << std::endl;
}
void printBatch(BTNode *root)
{
    if(root == NULL)
    {
        return ;
    }
    printPath(root);
    printBatch(root->lchild);
    printBatch(root->rchild);

}
void transfer2PostForFullBtHelp(int [], int, int);

void transfer2PostForFullBt(int a[], int length)
{
    transfer2PostForFullBtHelp(a, 0, length - 1);
}

void transfer2PostForFullBtHelp(int a[], int begin, int end)
{
    int temp = a[begin];
    int middle;
    if(end - begin == 2)
    {
        a[begin] = a[begin+1];
        a[begin+1] = a[end];
        a[end] = temp;
        return ;
    }
    middle = begin + (end - begin) /2;
    transfer2PostForFullBtHelp(a, begin + 1, middle);
    transfer2PostForFullBtHelp(a, middle + 1, end);
    for(int i = begin; i < end; i++)
    {
        a[i] = a[i+1];
    }
    a[end] = temp;

}


void countBT(BTNode *root, int &count)
{
    if(root == NULL)
    {
        return ;
    }
    count++;
    countBT(root->lchild, count);
    countBT(root->rchild, count);
}

void countBTLeaf(BTNode *root, int &count)
{
    if(root == NULL)
    {
        return ;
    }
    if(root->lchild == NULL && root->rchild == NULL)
    {
        count++;
        return ;
    }
    countBTLeaf(root->lchild, count);
    countBTLeaf(root->rchild, count);
}

void linkLeaf(BTNode *root, BTNode *&head, BTNode *&tail, BTNode *&prev)
{
    if(root == NULL)
    {
        return ;
    }
    linkLeaf(root->lchild, head, tail, prev);
    if(root->lchild == NULL && root->rchild == NULL)
    {
        tail = root;
        if(prev == NULL)
        {
            head = root;
            prev = head;
        }
        else
        {
            prev->rchild = root;
            prev = root;
        }

    }
    linkLeaf(root->rchild, head, tail, prev);
}
int levelOfBTHelp(BTNode *root, int x, int current)
{
    int result = -1;
    if(root == NULL)
    {
        return result;
    }
    if(root->data == x)
    {
        result = current;
        return result;
    }
    current++;
    result = levelOfBTHelp(root->lchild, x, current);
    if(result != -1)
    {
        return result;
    }
    result = levelOfBTHelp(root->rchild, x, current);
    return result;
}
int levelOfBT(BTNode *root, int x)
{
    int current = 1;
    return levelOfBTHelp(root, x, current);
}

void doubleIter(BTNode *root)
{
    if(root == NULL)
    {
        return;
    }
    std::cout << root->data << " ";
    doubleIter(root->lchild);
    std::cout << root->data << " ";
     doubleIter(root->rchild);
}

void allPath(BTNode *root)
{
    static int stack[maxSize];
    static int top=-1;
    if(root == NULL)
    {
        return;
    }
    top++;
    stack[top] = root->data;
    if(root->rchild == NULL && root->lchild == NULL)
    {
        for(int i = 0; i <= top;i++)
            std::cout <<  stack[i] << " ";
        std::cout << std::endl;
    }
    allPath(root->lchild);
    allPath(root->rchild);
    top--;

}

#endif //STRUCTURE_TREE_H
